The present invention relates to a method and apparatus for drawing wide lines in a raster graphics system, and more particularly to a laser printing or display system.
The development of laser printers and page description languages allow a user to create complex documents with graphics primitives -- lines, arcs and curves. The more complex the documents are, the more graphics primitives they use. Unfortunately, this approach means more processing time must be spent on rasterizing the primitives. Efficient processing of the graphics primitives by the printer's interpreter would increase throughput and likely improve the marketability of the printer.
Among the graphics primitives, line is the most often used. Laser printer interpreters often convert arcs and curves into contiguous line segments. Polygons are filled by repeatedly drawing lines over the area. Moreover, many fonts used in the laser printer systems are in outline forms, requiring the interpreter software to process the fonts as lines and arcs. Thus, a fast line drawing method is imperative for efficient graphics processing.
Line drawing in computer graphics is accomplished by turning on pixels on an imaginary square grid (page frame buffer). The pixels turned on must lie between the two end pixels in such a way that they approximate a line. There are well known algorithms to do this, most noticeably Bresenham's algorithm. On some graphics microprocessors, Bresenham's algorithm can be executed by single assembly instruction. For example, the TMS34010 microprocessor has a LINE instruction, along with parameter set up registers, which does the line drawing.
Bresenham's algorithm and the LINE instruction draws a line of width of one pixel. However, a single pixel line is rarely used in laser printing, since a typical laser printer's resolution is more than 300 dots per inch. A single pixel line often cannot be perceived by the human eye as a continuous line. For lines of width greater than one pixel, a wide line can be drawn with or without using the algorithm.
There are known algorithms to draw wide lines. One such algorithm widens a single pixel line by placing additional pixels on either side, or above and below each pixel. Whether to put additional pixels on side, or above and below, depends on the slope of the line being drawn. This algorithm's problem is that the line drawn is not rectangular unless it is vertical or horizontal, unless the resulting page is non-uniformly scaled (see FIG. 1). Typical page description language line is rectangular regardless of its slope (see FIG. 2). Also see pages 21-22 of Computer Graphics by Steven Harrington, and pages 167-168 of Graphics Programming in C by Roger T. Stevens.
In U.S. Pat. No. 4,819,185, rectangular wide line drawing is described regardless of the line's slope, but it effectively fills the holes generated by stacking Bresenham's lines to draw a wide line. However, that drawing method does not distinguish between sloped lines and non-sloped lines, horizontal and vertical. Distinguishing the non-sloped lines and sloped lines are crucial in the laser printer system employing TMS340xx processors, since the processor can fill a horizontal or vertical line (a rectangle) very efficiently using its rectangle fill instruction.